package com.company.test24;

import java.util.Comparator;

/**
 * Created by Administrator on 2016.10.20.
 */
public class Test2403 {
    public static void main(String[] args) {
        Integer[] a={2,5,3,4,7,34,2,34,6,4,6,9,6};
        quickSort(a);

        for(int i=0;i<a.length;i++){
            System.out.println(a[i]);
        }
    }

    public static <E extends Comparable<E>> void quickSort(E[] list){
        quickSort(list,0,list.length-1);
    }

    private static <E extends Comparable<E>> void quickSort(E[] list,int first,int last){
        if(last<=first){
            return;
        }

        int p=partition(list,first,last);

        quickSort(list,first,p-1);
        quickSort(list,p+1,last);
    }

    private static <E extends Comparable<E>> int partition(E[] list,int first,int last){

        E pivot=list[first];
        int low=first+1;
        int high=last;

        while (high>low){
            while (high>=low&&list[low].compareTo(pivot)<=0){
                low++;
            }

            while (high>=low&&list[high].compareTo(pivot)>0){
                high--;
            }

            if(high>low){
                E temp=list[high];
                list[high]=list[low];
                list[low]=temp;
            }
        }

        if(pivot.compareTo(list[high])>=0){
            list[first]=list[high];
            list[high]=pivot;
            return high;
        }else {
            return first;
        }
    }
}
